#pragma once

#include <vector>
#include <utility>

namespace sorting
{
    // 实现细节的命名空间
    namespace impl
    {
        /**
         * @brief           返回中间值的索引
         * @tparam  T       基本数据类型
         * @param   vec     基本数据类型的数组（常引用）
         * @param   left    数组的左边界
         * @param   right   数组的右边界
         */
        template <typename T>
        std::size_t medianOfThree(const std::vector<T> &vec, std::size_t left, std::size_t right)
        {
            using std::size_t;

            if (left + 2 > right)
            {
                // 当左右边界相差不太大时，不需要取中
                return left;
            }

            size_t mid = left + (right - left) / 2;
            const T l = vec[left], m = vec[mid], r = vec[right];

            // 比较三个元素，返回中间值的索引
            if (l < m)
            {
                if (m < r)
                {
                    // vec[left] < vec[mid] < vec[right]
                    return mid;
                }
                else if (l < r)
                {
                    // vec[left] < vec[right] <= vec[mid]
                    return right;
                }
                else
                {
                    // vec[right] <= vec[left] < vec[mid]
                    return left;
                }
            }
            else
            {
                if (l < r)
                {
                    // vec[mid] <= vec[left] < vec[right]
                    return left;
                }
                else if (m < r)
                {
                    // vec[mid] < vec[right] <= vec[left]
                    return right;
                }
                else
                {
                    // vec[right] <= vec[mid] <= vec[left]
                    return mid;
                }
            }
        }

        /**
         * @brief           哨兵划分函数
         * @note            应用了“三数取中”
         * @tparam  T       基本数据类型
         * @param   vec     基本数据类型的数组
         * @param   left    数组的左边界
         * @param   right   数组的右边界
         */
        template <typename T>
        std::size_t partition(std::vector<T> &vec, std::size_t left, std::size_t right)
        {
            using std::size_t;
            using std::swap;

            // 以vec[left]为基准值
            size_t med = medianOfThree(vec, left, right);

            // 将中位数交换到数组最左端
            swap(vec[left], vec[med]);

            const T pivot = vec[left]; // 保存基准值
            size_t i = left, j = right;
            while (i < j)
            {
                while (i < j && vec[j] >= pivot)
                {
                    // 从右向左找首个小于基准数的元素
                    j--;
                }
                while (i < j && vec[i] <= pivot)
                {
                    // 从左向右找首个大于基准数的元素
                    i++;
                }
                if (i < j)
                {
                    swap(vec[i], vec[j]);
                }
            }

            // 将基准数交换到两个子数组的分界线处
            swap(vec[i], vec[left]);
            return i;
        }
    } // namespace impl

    /**
     * @brief           快速排序
     * @note            应用了尾递归优化
     * @tparam  T       基本数据类型
     * @param   vec     基本数据类型的数组
     * @param   left    数组的左边界
     * @param   right   数组的右边界
     */
    template <typename T>
    void QuickSort(std::vector<T> &vec, std::size_t left, std::size_t right)
    {
        using std::size_t;

        // 基准情况
        if (left >= right)
        {
            return;
        }

        size_t pivot = impl::partition(vec, left, right);

        // 防止无符号整数下溢
        if (pivot > left)
        {
            QuickSort(vec, left, pivot - 1);
        }
        if (pivot < right)
        {
            QuickSort(vec, pivot + 1, right);
        }
    }

    /**
     * @brief       快速排序（便捷版本）
     * @tparam  T   基本数据类型
     * @param   vec 基本数据类型的数组
     */
    template <typename T>
    void QuickSort(std::vector<T> &vec)
    {
        std::size_t len = vec.size();
        if (len <= 1)
        {
            return;
        }

        QuickSort(vec, 0, len - 1);
    }
} // namespace sorting